package leetcode.editor.cn;

//编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 
//
// 示例1: 
//
// 
// 输入：[1, 2, 3, 3, 2, 1]
// 输出：[1, 2, 3]
// 
//
// 示例2: 
//
// 
// 输入：[1, 1, 1, 1, 2]
// 输出：[1, 2]
// 
//
// 提示： 
//
// 
// 链表长度在[0, 20000]范围内。 
// 链表元素在[0, 20000]范围内。 
// 
//
// 进阶： 
//
// 如果不得使用临时缓冲区，该怎么解决？ 
// Related Topics 链表

import com.alibaba.fastjson.JSON;
import lombok.Data;

import java.util.HashSet;
import java.util.Set;

public class RemoveDuplicateNodeLcci{
    public static void main(String[] args) {
        Solution solution = new RemoveDuplicateNodeLcci().new Solution();
        ListNode node = new ListNode(1);
        node.next = new ListNode(2);
        node.next.next = new ListNode(1);
        System.out.println(JSON.toJSONString(solution.removeDuplicateNodes(node)));
    }

    @Data
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
  }
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    Set<Integer> set = new HashSet<>();
    public ListNode removeDuplicateNodes(ListNode head) {
        if (head==null)//说明到了链表尾端
            return null;
        if (!set.contains(head.val)){//这个值第一次出现
            set.add(head.val);//set中加入这个值，防止再次出现
            head.next=removeDuplicateNodes(head.next);//保留此节点，对下一个节点继续验证
            return head;
        }
        else{//这个值不是第一次出现

            //当前节点不要，返回对下一个节点的验证，注意这里返回的也是一个链表
            // 的一部分，返回的节点会直接挂到上次个只出现一次的节点下面。如果说
            //链表不为空，呢么一定会有至少一个节点在上面，也就是满足过if条件的，
            //那么根据if中的代码，head.next就是这里返回的。
            return removeDuplicateNodes(head.next);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}